package independent;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-11-15
 * Time: 10:10
 */

//希尔排序 更高效的插入排序 也叫缩小增量排序
public class ShellSort {
    //原理:希尔排序就是先分组(分的不知一组 增量在较少) 然后插入
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};

        shellSort1(arr);

        System.out.println(Arrays.toString(arr));

    }


    //交换法
    private static void shellSort(int[] arr) {
        //先进行分组
        int tmp = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int j = gap; j < arr.length; j++) {
                //然后对分出来的组 直接插入排序
                for (int i =j-gap; i >= 0; i -= gap) {
                    if (arr[i] > arr[i+gap]){
                        tmp = arr[i];
                        arr[i] = arr[i+gap];
                        arr[i+gap] = tmp;
                    }
                }
            }
        }
    }

    //移位法
    private static void shellSort1(int[] arr) {
        //先分组 然后逐步减小
        for (int gap = arr.length/2; gap > 0 ; gap /= 2) {
            //从第gap个元素开始 逐个对其所在元素直接插入排序
            for (int i = gap; i < arr.length ; i++) {
                //记录要交换 和 下标
                int j = i;
                int tmp = arr[i];
                if (arr[j] < arr[j-gap]){
                    while (j-gap >= 0 && tmp < arr[j-gap]){
                        //移动
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    arr[j] = tmp;
                }
            }
        }
    }
    
    
}














